/*
 * The RavenX Library
 * Copyright (c) 2008 by Solidus
 * 
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.It is provided "as is" without express 
 * or implied warranty.
 *
 */
#include "rx_list.h"
#include "rx_debug.h"
#include "rx_misc.h"
#include "rx_mem.h"
#include <stdarg.h>
RX_SPACE_BEG



typedef struct __rx_list_node_tag
{
		rx_list_node_t	*prev;
		rx_list_node_t	*next;
}rx_list_node_t;

#define __node_size(e_size) ((e_size) + sizeof(rx_list_node_t))
#define __node_data(node)   ((void*)((rx_byte*)node + sizeof(rx_list_node_t)))



void*			rx_list_node_data(rx_list_node_t *node)
{
		return (void*)(node != NULL ? __node_data(node) : NULL);
}



typedef struct __rx_list_tag
{
		rx_info_t				info;
		rx_alloc_t				alloc;

		size_t					count;
		rx_list_node_t			header;
}rx_list_t;



/*********************************************************************************************************************************************************/
static RX_INLINE rx_bool __list_is_valid(const rx_list_t *self)
{
		if(self != NULL 
				&& self->info.elem_size > 0 
				&& self->info.init_f != NULL
				&& self->info.uninit_f != NULL
				&& self->info.copy_f != NULL
				&& self->info.cmp_f != NULL
				&& self->alloc.alloc_f != NULL
				&& self->alloc.dealloc_f != NULL
				&& self->alloc.realloc_f != NULL
				)
		{
				if(self->count > 0)
				{
						return (self->header.prev != &self->header && self->header.next != &self->header) ? rx_true : rx_false;
				}else
				{
						return (self->header.prev == &self->header && self->header.next == &self->header) ? rx_true : rx_false;

				}
		}else
		{
				return rx_false;
		}

		
}

static RX_INLINE rx_list_node_t* __create_node(const void *data, rx_list_node_t *prev, rx_list_node_t *next, rx_list_t *self)
{
		rx_list_node_t *node;
		RX_ASSERT(__list_is_valid(self));
		RX_ASSERT(data != NULL);
		node = (rx_list_node_t*)self->alloc.alloc_f(__node_size(self->info.elem_size), self->alloc.ctx);
		self->info.copy_f(__node_data(node), data, self->info.elem_size);

		node->prev = prev;
		node->next = next;
		return node;
}


static RX_INLINE void __destroy_node(rx_list_node_t *node, rx_list_t *self)
{
		RX_ASSERT(__list_is_valid(self));
		RX_ASSERT(node != NULL);
		
		self->info.uninit_f(__node_data(node), self->info.elem_size);
		self->alloc.dealloc_f(node, self->alloc.ctx);
}

/*********************************************************************************************************************************************************/


rx_list_node_t* rx_list_node_next(const rx_list_t *self, rx_list_node_t *node)
{
		RX_ASSERT(__list_is_valid(self));
		if(node == NULL)return NULL;

		if(node->next == &self->header) return NULL;

		return node->next;
		

}


rx_list_node_t* rx_list_node_prev(const rx_list_t *self, rx_list_node_t *node)
{
		RX_ASSERT(__list_is_valid(self));
		if(node == NULL)return NULL;

		if(node->prev == &self->header) return NULL;

		return node->prev;

}

rx_list_node_t* rx_list_head(rx_list_t *self)
{
		RX_ASSERT(__list_is_valid(self));

		if(self->header.next != &self->header) return self->header.next;
		
		RX_ASSERT(self->count == 0);
		return NULL;
}

rx_list_node_t* rx_list_tail(rx_list_t *self)
{
		RX_ASSERT(__list_is_valid(self));

		if(self->header.prev != &self->header) return self->header.prev;
		RX_ASSERT(self->count == 0);
		return NULL;
}





static RX_INLINE void __init_list(rx_list_t *out, const rx_info_t *pinfo, const rx_alloc_t *palloc)
{
		
		RX_ASSERT(pinfo != NULL &&palloc != NULL);
		rx_memset(out, 0, sizeof(rx_list_t));
		out->info = *pinfo;
		rx_install_info(&(out->info));
		out->alloc = *palloc;
		

		out->header.prev = out->header.next = &out->header;
}


RavenAPI rx_list_t*		rx_list_create(const rx_info_t *pinfo, const rx_alloc_t *palloc)
{
		rx_list_t* res;
		RX_ASSERT(pinfo != NULL && pinfo->elem_size > 0);
		if(palloc == NULL)palloc = rx_mem_default_alloctor();
		RX_ASSERT(palloc->alloc_f != NULL && palloc->dealloc_f != NULL && palloc->realloc_f != NULL);
		
		res = (rx_list_t*)palloc->alloc_f(sizeof(rx_list_t),palloc->ctx);
		__init_list(res, pinfo, palloc);
		
		return res;
}



void			rx_list_destroy(rx_list_t* self)
{
		if(self == NULL)return;

		RX_ASSERT(__list_is_valid(self));

		rx_list_clear(self);

		self->alloc.dealloc_f(self,   self->alloc.ctx);

}


void			rx_list_clear(rx_list_t* self)
{
		RX_ASSERT(__list_is_valid(self));
		rx_list_erase_range(self, rx_list_head(self), NULL);
		RX_ASSERT(self->header.next == &self->header && self->header.prev == &self->header);
}


rx_list_t*		rx_list_copy(const rx_list_t* self)
{
		rx_list_t* new_list;
		rx_list_node_t *curr;
		RX_ASSERT(__list_is_valid(self));
		
		new_list = rx_list_create(&self->info, &self->alloc);

		for(curr = rx_list_head((rx_list_t*)self); curr != NULL; curr = rx_list_node_next((rx_list_t*)self, curr))
		{
				rx_list_insert(new_list, NULL, __node_data(curr));
		}
		return new_list;
}


rx_list_node_t* rx_list_insert(rx_list_t *self, rx_list_node_t *pos, const void *data)
{
		rx_list_node_t*new_node;
		RX_ASSERT(__list_is_valid(self));

		if(pos == NULL)pos = &self->header;
		new_node = __create_node(data, pos->prev, pos, self);
		
		RX_FATAL_ERROR(new_node != NULL);
		
		new_node->prev->next = new_node;
		new_node->next->prev = new_node;
		self->count++;
		return new_node;
}

rx_list_node_t* rx_list_erase_node(rx_list_t *self, rx_list_node_t *node)
{
		rx_list_node_t *prev_node, *next_node;
		RX_ASSERT(__list_is_valid(self));
		RX_ASSERT(node != NULL);
		
		prev_node = node->prev;
		next_node = node->next;
		prev_node->next = next_node;
		next_node->prev = prev_node;
		self->count--;
		__destroy_node(node, self);
		
		return (next_node != &self->header ? next_node : NULL);
}

size_t			rx_list_size(const rx_list_t *self)
{
		RX_ASSERT(__list_is_valid(self));
		return self->count;

}

rx_bool		rx_list_is_empty(const rx_list_t *self)
{
		RX_ASSERT(__list_is_valid(self));
		
		if(rx_list_size(self) == 0)
		{
				RX_ASSERT(self->header.next == &self->header && self->header.prev == &self->header);
				return rx_true;
		}else
		{
				return rx_false;
		}
}

rx_list_node_t* rx_list_erase_range(rx_list_t *self, rx_list_node_t *first, rx_list_node_t *last)
{
		RX_ASSERT(__list_is_valid(self));
		
		while(first != last) first = rx_list_erase_node(self, first);
		
		return first;

}

rx_list_node_t* rx_list_index(rx_list_t *self, size_t idx)
{
		rx_list_node_t *node;
		size_t i;
		RX_ASSERT(__list_is_valid(self) && idx < self->count);
		if(idx >= self->count)return NULL;
			
		node = rx_list_head(self);
		i = 0;

		while(i < idx)
		{
				node = rx_list_node_next(self,node);
				i++;
		}
		
		
		RX_ASSERT(node != NULL);
		return node;
}

void*			rx_list_at(rx_list_t *self, size_t idx)
{
		rx_list_node_t *node;
		RX_ASSERT(__list_is_valid(self) && idx < self->count);
		node = rx_list_index(self,idx);
		if(node == NULL)return NULL;
		return __node_data(node);
}


static RX_INLINE size_t __count_node(rx_list_t *self, rx_list_node_t *first, rx_list_node_t *last)
{
		size_t n;
		RX_ASSERT(__list_is_valid(self) && first != NULL);
		if(last == NULL)last = &self->header;
		n = 0;

		while(first != last)
		{
				first = first->next; 
				++n;
		}
		return n;
}

void			rx_list_splice_range(rx_list_t *self, rx_list_node_t *pos, rx_list_t *sour, rx_list_node_t *first, rx_list_node_t *last)
{
		
		rx_list_node_t *tmp;
		size_t			n;
		RX_ASSERT(__list_is_valid(self));
		RX_ASSERT( __list_is_valid(sour));
		RX_ASSERT(first != NULL);

		if(pos == first ||  first == last)return;
		
		n = __count_node(sour, first, last);

		if(pos == NULL) pos = &self->header;
		if(last == NULL)last = &sour->header;

		
		last->prev->next = pos;
		first->prev->next = last;
		pos->prev->next = first;
		tmp = pos->prev;
		pos->prev = last->prev;
		last->prev = first->prev;
		first->prev = tmp;

		self->count += n;
		sour->count -= n;
}




void			rx_list_reverse(rx_list_t *self)
{
		rx_list_node_t *curr;
		RX_ASSERT(__list_is_valid(self));
		if(self->count < 2)return;
		
		curr = self->header.next->next;
		
		while(curr != &self->header)
		{
				curr = curr->next;
				rx_list_splice_range(self, self->header.next, self, curr->prev, (curr != &self->header ? curr : NULL));
		}
}






size_t rx_list_insert_args(rx_list_t *self, const void *data, ...)
{
		size_t n;
		va_list mark = NULL;
		
		RX_ASSERT(__list_is_valid(self));
		n = 0;
		va_start(mark, data);

		do{
				rx_list_insert(self, NULL, data);
				n++;
		}while((data = va_arg(mark, const void*)) != NULL);

		return n;
}

size_t rx_list_insert_args_count(rx_list_t *self, size_t count, const void *data, ...)
{
		size_t i;

		va_list mark = NULL;
		
		RX_ASSERT(__list_is_valid(self));
		i = 0;
		va_start(mark, data);

		while(i++ < count) 
		{
				rx_list_insert(self, NULL, data);
				data = va_arg(mark, const void*);
		}
		return count;
}


void			rx_list_merge(rx_list_t *self, rx_list_t *other)
{
		int cmp; int (*cmp_f)(const void *l, const void *r, size_t esize);
		rx_list_node_t *curr1, *curr2, *last1, *last2;
		RX_ASSERT(__list_is_valid(self));
		RX_ASSERT(__list_is_valid(other));
		RX_ASSERT(rx_memcmp((const void*)&self->info, (const void*)&other->info, sizeof(rx_info_t)) == 0);
		RX_ASSERT(self != other);
		cmp_f = self->info.cmp_f;
		

		curr1 = self->header.next;
		last1 = &self->header;
		curr2 = other->header.next;
		last2 = &other->header;

		while(curr1 != last1 && curr2 != last2)
		{
				cmp = cmp_f(__node_data(curr1), __node_data(curr2), self->info.elem_size);

				if(cmp < 0)
				{
						curr1 = curr1->next;
				}else
				{
						rx_list_splice_range(self, curr1, other,other->header.next,  (curr2->next != last2 ? curr2->next : NULL));
						curr2 = other->header.next;
				}
		}

		if(other->count > 0)rx_list_splice_range(self, NULL, other, other->header.next, NULL);

		
		RX_ASSERT(__list_is_valid(self));
		RX_ASSERT(__list_is_valid(other));
		RX_ASSERT(other->count == 0 && other->header.next == &other->header && other->header.prev == &other->header);

		
		
}

void			rx_list_unique(rx_list_t *self)
{
		int cmp; int (*cmp_f)(const void *l, const void *r, size_t esize);
		rx_list_node_t *curr, *next_node;
		
		RX_ASSERT(__list_is_valid(self));
		cmp_f = self->info.cmp_f;
		
		RX_ASSERT(cmp_f != NULL);

		curr = rx_list_head(self);
		next_node = rx_list_node_next(self, curr);
		
		while(next_node != NULL)
		{
				cmp = cmp_f(__node_data(curr), __node_data(next_node), self->info.elem_size);

				if(cmp != 0)
				{
						curr = rx_list_node_next(self, curr);
						next_node = rx_list_node_next(self, curr);
				}else
				{
						next_node = rx_list_erase_node(self, next_node);
				}
		}

}


size_t			rx_list_remove(rx_list_t *self, const void *data)
{
		size_t	n;
		int (*cmp_f)(const void *l, const void *r, size_t esize);
		rx_list_node_t *curr;
		RX_ASSERT(__list_is_valid(self));
		cmp_f = self->info.cmp_f;
		RX_ASSERT(cmp_f != NULL);
		
		n = 0;
		curr = rx_list_head(self);
		while(curr != NULL)
		{
				if(cmp_f(__node_data(curr), data, self->info.elem_size) == 0)
				{
						curr = rx_list_erase_node(self, curr);
						n++;
				}else
				{
						curr = rx_list_node_next(self, curr);
				}
		}
		return n;
}


void			rx_list_swap(rx_list_t *self, rx_list_t *other)
{
		rx_list_t	ltmp;
		RX_ASSERT(__list_is_valid(self));
		RX_ASSERT(__list_is_valid(other));

		
		if(!rx_list_is_empty(self) && !rx_list_is_empty(other))
		{
				rx_list_node_t *tmp;
				self->header.next->prev = &other->header;
				self->header.prev->next = &other->header;
				other->header.next->prev = &self->header;
				other->header.prev->next = &self->header;
				tmp = self->header.next;
				self->header.next = other->header.next;
				other->header.next = tmp;
				tmp = self->header.prev;
				self->header.prev = other->header.prev;
				other->header.prev = tmp;
		}else if(rx_list_is_empty(self) && !rx_list_is_empty(other))
		{
				self->header.next = other->header.next;
				self->header.prev = other->header.prev;
				other->header.next = other->header.prev = &other->header;

				self->header.next->prev = &self->header;
				self->header.prev->next = &self->header;
		}else if(!rx_list_is_empty(self) && rx_list_is_empty(other))
		{
				other->header.next = self->header.next;
				other->header.prev = self->header.prev;
				self->header.next = self->header.prev = &self->header;
				other->header.next->prev = &other->header;
				other->header.prev->next = &other->header;
		}

		ltmp = *self;
		self->info = other->info;
		self->alloc = other->alloc;
		self->count = other->count;

		other->info = ltmp.info;
		other->alloc = ltmp.alloc;
		other->count = ltmp.count;

		RX_ASSERT(__list_is_valid(self));
		RX_ASSERT(__list_is_valid(other));
}


#define __TEMP_LIST_N (sizeof(rx_uint_n) * 8)

#define __TEMP_LIST_BUF_SIZE (sizeof(rx_list_t) * __TEMP_LIST_N)

void			rx_list_sort(rx_list_t *self)
{
		int (*cmp_f)(const void *l, const void *r, size_t esize);
		int i, fill;
		rx_list_t		*tmp_list = NULL;
		rx_list_t		carry;
		rx_list_node_t	*tmp;
		RX_ASSERT(__list_is_valid(self));
		cmp_f = self->info.cmp_f;
		RX_ASSERT(cmp_f != NULL);

		if(self->count < 2)return;

		tmp_list = (rx_list_t*)self->alloc.alloc_f(__TEMP_LIST_BUF_SIZE, self->alloc.ctx);
		
		RX_FATAL_ERROR(tmp_list != NULL);

		for(i = 0; i < __TEMP_LIST_N; ++i) __init_list(tmp_list + i, &self->info, &self->alloc);

		__init_list(&carry, &self->info, &self->alloc);

		fill = 0;

		while(!rx_list_is_empty(self))
		{
				RX_ASSERT(rx_list_is_empty(&carry));
				tmp = rx_list_head(self);
				rx_list_splice_range(&carry, NULL, self, tmp, rx_list_node_next(self, tmp));
				
				i = 0;
				while(i < fill && !rx_list_is_empty(tmp_list + i))
				{
						rx_list_merge(tmp_list + i, &carry);

						RX_ASSERT(rx_list_is_empty(&carry));
						
						rx_list_swap(tmp_list + i, &carry);

						i++;
				}
				
				if(i == fill) fill++;
				rx_list_swap(tmp_list + i, &carry);
		}

		for(i = 1; i < fill; ++i)rx_list_merge(tmp_list + i, tmp_list + (i - 1));
		
		rx_list_swap(self, tmp_list + (fill - 1));

		self->alloc.dealloc_f(tmp_list,   self->alloc.ctx);

		RX_ASSERT(__list_is_valid(self));
}




void			rx_list_push_back(rx_list_t *self, const void *data)
{
		RX_ASSERT(__list_is_valid(self));

		rx_list_insert(self, NULL,data);

}

void			rx_list_push_front(rx_list_t *self, const void *data)
{
		RX_ASSERT(__list_is_valid(self));
		rx_list_insert(self, rx_list_head(self), data);
}


void	rx_list_pop_back(rx_list_t *self)
{
		RX_ASSERT(__list_is_valid(self));
		
		rx_list_erase_node(self, rx_list_tail(self));

}


void			rx_list_pop_front(rx_list_t *self)
{
		RX_ASSERT(__list_is_valid(self));
		
		rx_list_erase_node(self, rx_list_head(self));

}




rx_list_node_t* rx_list_find_pos(rx_list_t *self, rx_list_node_t *start, rx_list_node_t *end, const void *key)
{
		rx_list_node_t	*res;
		int (*cmp_f)(const void *l, const void *r, size_t esize);

		RX_ASSERT(__list_is_valid(self));
		cmp_f = self->info.cmp_f;
		RX_ASSERT(cmp_f != NULL);

		res = (start == NULL ? rx_list_head(self) : start);

		while(res != NULL && res != end)
		{
				if(cmp_f(__node_data(res),key, self->info.elem_size) == 0)return res;
				res = rx_list_node_next(self, res);
		}
		
		return NULL;
		

}

size_t rx_list_erase_equal(rx_list_t *self, const void *key)
{
		rx_list_node_t	*curr;
		size_t n;
		RX_ASSERT(__list_is_valid(self));
		
		n = 0;
		curr = NULL;
		
		do{
				curr = rx_list_find_pos(self, curr, NULL, key);
				if(curr == NULL)break;
				curr = rx_list_erase_node(self, curr);
				n++;
		}while(curr != NULL);

		return n;
}




size_t rx_list_insert_range(rx_list_t *self, rx_list_node_t *pos, rx_list_t *sour, rx_list_node_t *start, rx_list_node_t *end)
{
		size_t n;
		RX_ASSERT(__list_is_valid(self));
		RX_ASSERT(__list_is_valid(sour));
		n = 0;
		while(start != end)
		{
				rx_list_insert(self, pos, rx_list_node_data(start));
				start = rx_list_node_next(sour, start);
				n++;
		}
		
		return n;
}



RX_SPACE_END
